class Solution
{
public:
    int nthUglyNumber(int n)
    {
        int f[n + 1];
        f[1] = 1;
        int p1 = 1, p2 = 1, p3 = 1;
        for (int i = 2; i <= n; i++)
        {
            int num1 = f[p1] * 2, num2 = f[p2] * 3, num3 = f[p3] * 5;
            f[i] = min(min(num1, num2), num3);
            if (f[i] == num1)
            {
                ++p1;
            }
            if (f[i] == num2)
            {
                ++p2;
            }
            if (f[i] == num3)
            {
                ++p3;
            }
        }
        return f[n];
    }
};